Back أطروحة تشرش-تورينغ Arabic Тезис на Чърч Bulgarian Tesi de Church-Turing Catalan Churchova–Turingova teze Czech Church-Turing-tesen Danish Church–Turing thesis English Ĉurĉa tezo Esperanto Tesis de Church-Turing Spanish Churchi tees Estonian تز چرچ-تورینگ Persian
Die Church-Turing-These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet:
„Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.“[1]
Diese These ist nicht beweisbar, da der Begriff „intuitiv berechenbare Funktion“ nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auf irgendeine Weise berechnet werden könnten. Damit setzt man insbesondere keine Vorstellung voraus, welche Funktionen auf den natürlichen Zahlen berechenbar sind. Es wird in der Informatik üblicherweise angenommen, dass die These stimmt. Dadurch wird es möglich, für eine Funktion nachzuweisen, dass sie nicht berechenbar ist.
- ↑ Dirk W. Hoffmann: Theoretische Informatik. 2., aktualisierte Auflage. Carl Hanser Fachbuchverlag, München 2011, ISBN 978-3-446-42639-9, S. 308.